﻿<?php
class Ordenacao{
	
	public $comparacao=0;
	public $trocas=0;
	
	public function bubblesort($n, $v){
		$trocou= 1;
		for($pass= 0; $pass< $n-1 && $trocou; $pass++){
			$trocou= 0;
			for($j=0; $j< $n-$pass-1; $j++){
				
				//Número de Comparações
				$this->comparacao++;
				if($v[$j]> $v[$j+1]){
					$trocou= 1;
					$aux= $v[$j];
					$v[$j]= $v[$j+1];
					$v[$j+1]= $aux;
					//Trocas
					$this->trocas++;
				}
			}
		}
		
		return $v;
	}
	
	public function quicksort(&$v, $esq, $dir){
		$i= $esq;
		$j= $dir;
		$p= $v[(int)($i+$j)/2];
		do{
			while($v[$i]< $p){
				$i++;
			}
			while($p< $v[$j]){
				$j--;
			}
			//Número de Comparações
			$this->comparacao++;
			if($i<= $j){
				$salva= $v[$i];
				$v[$i]= $v[$j];
				$v[$j]= $salva;
				$i++;
				$j--;
				//Trocas
				$this->trocas++;
			}
		}while($i<= $j);
		if($esq< $j){
			$this->quicksort($v, $esq, $j);
		}
		if($i< $dir){
			$this->quicksort($v, $i, $dir);
		}
		
		return $v;
	}
	
	public function insercao_Direta($v, $n){
		for($i=1; $i< $n; $i++){
			//Número de Comparações
			$this->comparacao++;
			$salva= $v[$i];
			$j= $i- 1;
			while ($salva< $v[$j] && $j>=0){
				//Número de Comparações
				$this->comparacao++;
				//Trocas
				$this->trocas++;
				$v[$j+1]= $v[$j]; 
				$j= $j- 1;
			}
			$v[$j+1]= $salva;
			
		}
		
		return $v;
	}
	public function shellsort($n, $v){
		
		do{
				
				(int)$h = (int)$h * 3+ 1;
			
			}while ((int)$h < $n);
			do{
				(int)$h/= 3;
				
				for($i= (int)$h; $i< $n; $i++){
					//Trocas
					$this->trocas++;
					$salva= $v[$i];
					$j= $i;
					
					while($v[$j- (int)$h]> $salva){
						//Número de Comparações
						$this->comparacao++;
						
						$v[$j]= $v[$j- (int)$h];
						$j= $j- (int)$h;
						
						//Trocas
						$this->trocas++;
						if($j< (int)$h){
							break;
						}
					}
					//Trocas
					$this->trocas++;
					$v[$j]= $salva;
				}
		}while((int)$h!= 1);
		
		return $v;
	}
	
	public function selecao_Direta($n, $v){
		for($i=0; $i< $n-1; $i++){
			$menor= $v[$i];
			$pos_Menor= $i;
			for($j= $i+ 1; $j< $n; $j++){
				//Número de Comparações
				$this->comparacao++;
				if($v[$j]< $menor){
					$menor= $v[$j];
					$pos_Menor= $j;
					//Trocas
					$this->trocas++;
				}
			}
			$v[$pos_Menor]= $v[$i];
			$v[$i]= $menor;
		}
		
		return $v;
	}
	
	public function constroi_Heap($n, $v){
		for($m= 1; $m< $n; $m++){
			(int)$f= $m+ 1;
			while((int)$f> 1 && $v[(int)$f/ 2]< $v[(int)$f]){
				//Trocas
				$this->trocas++;
				$t= $v[(int)$f/2];
				$v[(int)$f/2]= $v[(int)$f];
				$v[(int)$f]= $t;
				(int)$f= (int)$f/ 2;
			}		
		}
		
		return $v;
	}
	
	public function heapsort($n, $v){
		$this->constroi_Heap($n, $v);
		for($m= $n; $m> $n; $m--){
			$max= $v[1];
			(int)$f= 2;
			while((int)$f<= m){
				//Número de Comparações
				$this->comparacao++;
				if((int)$f< $m && $v[(int)$f]< $v[(int)$f+1]){
					(int)++$f;
				}
				$v[(int)$f/2]= $v[(int)$f];
				(int)$f *= 2;
			}
			(int)$f= (int)$f/2;
				//Número de Comparações
				$this->comparacao++;
				if((int)$f< $m){
					//Trocas
					$this->trocas++;
					$t = $v[(int)$f];
					$v[(int)$f] = $v[$m];
					$v[$m] = $t;
					
					while((int)$f > 1 && $v[(int)$f/2] < $v[(int)$f]) {
							//Trocas
							$this->trocas++;
					   		$t = $v[(int)$f];
							$v[(int)$f] = $v[(int)$f/2];
							$v[(int)$f/2] = $t; 
					   		(int)$f = (int)$f/2; 
					} 	
				}
			$v[$m] = max;
		}
		return $v;
	}
	
}
?>